• Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.

Programming |OT| C is better than C++! No, C++ is better than C

I am wondering if I am overthinking this but in a fully-connected, undirected graph, the shortest path between a set of vertices, V1 - V10 would just be a direct route from V1 to V10, correct? If the graph is fully-connected, I can get from V1-V10 instantly. I feel like that's too simple so I am wondering if I am neglecting something.
 
I am wondering if I am overthinking this but in a fully-connected, undirected graph, the shortest path between a set of vertices, V1 - V10 would just be a direct route from V1 to V10, correct? If the graph is fully-connected, I can get from V1-V10 instantly. I feel like that's too simple so I am wondering if I am neglecting something.

If the weight of all connections is 1, yes. Otherwise, another path could potentially be shorter.
 
If the weight of all connections is 1, yes. Otherwise, another path could potentially be shorter.

The weights are Vi + Vj, where V represents a vertex. So, I suppose the weights from V1 to V6 would be 7. Therefore, V1 to V10 would be 11. I think it would be the case that the shortest path would be a direct route then.
 

Kansoku

Member
I am wondering if I am overthinking this but in a fully-connected, undirected graph, the shortest path between a set of vertices, V1 - V10 would just be a direct route from V1 to V10, correct? If the graph is fully-connected, I can get from V1-V10 instantly. I feel like that's too simple so I am wondering if I am neglecting something.

If the edges all have the same weight, then yes, else not necessarily.

EDIT: beaten
 

Koren

Member
I'm really liking Scala the more I do it. It feels like the lazy man's way to write Java code.
Are you before or after the WTF part?

I was promised it was a step in learning Scala, I've not been disappointed. It can be really really ugly, and there's so many ways to approach a problem that it's really non team-friendly. But I still enjoy it a lot.

I'm happy that someone suggested me to learn it instead of Go (coming from a Google developper, but he only had bad things to say about Go ^_^) but I'm glad I could learn it slowly, it must be awful to learn it in a matter of weeks.

The only thing I'm not fond with Scala is the JVM reliance, but I hate JVMs (with only half-valid reasons).
 

Slo

Member
Are you before or after the WTF part?

I was promised it was a step in learning Scala, I've not been disappointed. It can be really really ugly, and there's so many ways to approach a problem that it's really non team-friendly. But I still enjoy it a lot.

I'm happy that someone suggested me to learn it instead of Go (coming from a Google developper, but he only had bad things to say about Go ^_^) but I'm glad I could learn it slowly, it must be awful to learn it in a matter of weeks.

The only thing I'm not fond with Scala is the JVM reliance, but I hate JVMs (with only half-valid reasons).

I'm only working on personal projects so far, and my Scala code would best be described as ported-Java code, nothing too wild yet.

I guess I must still be "before" the WTF part. :)
 

Fou-Lu

Member
I found this list of online courses to do a bachelor's degree worth of comp sci on your own time: http://blog.agupieware.com/2014/06/online-learning-intensive-bachelors.html

Is it any good?

If I want to career change to a software developer/possible game dev and have only really used code for statistics and physics purposes, which courses would you recommend I go through? I have been considering going to UBC for their BCS program, which lets you get a second bachelor's in CS in two years, but since I already use programming for my Physics research I thought self-teaching might be more viable.
 

Slo

Member
I found this list of online courses to do a bachelor's degree worth of comp sci on your own time: http://blog.agupieware.com/2014/06/online-learning-intensive-bachelors.html

Is it any good?

If I want to career change to a software developer/possible game dev and have only really used code for statistics and physics purposes, which courses would you recommend I go through? I have been considering going to UBC for their BCS program, which lets you get a second bachelor's in CS in two years, but since I already use programming for my Physics research I thought self-teaching might be more viable.

Looks like it's basically just a list of courses that are freely available from some pretty good institutions. I mean, yeah, of course the content is good. I'm sure the content put out by MIT, Harvard and Stanford is worth your time going through as an educational exercise. But you seem to be doing this for the purposes of getting a job at the end, in which case I'd say that if you're not actually going to get a piece of paper that says BS in CompSci on it, then you're kind of dragging yourself through a lot of mucky trenches when you should probably be focusing on building a portfolio and learning skills that are more directly applicable to an entry level job.

Introductory Courses

Intro to Computer Science, pick two of three:
Introduction to Computer Science and Programming: MIT
Intensive Introduction to Computer Science: Harvard
Introduction to Computer Science and Programming Methodology: Stanford
Programming Abstractions (Second Course in Unit): Stanford
Basic mathematics, pick one of two:
Mathematics for Computer Science: MIT
Discrete Mathematics: ArsDigita

Core Courses

Data Structures and Algorithms, pick one of two:
Introduction to Data Structures and Algorithms: UNSW
Introduction to Algorithms: MIT
Operating Systems:
Operating Systems and Systems Programming: Berkeley
Programming Languages and Methodologies:
Programming Paradigms: Stanford
Computer Architecture:
Computer Architecture: Carnegie Mellon
Networking:
Fundamentals of Computer Networking: Manhattan College
Data Communications:
Introduction to Data Communications: Thammasat University
Cryptography and Security:
Introduction to Cryptography: Ruhr University

Electives

Web Development:
Building Dynamic Websites: Harvard
Data Structures:
Advanced Data Structures: MIT
Systems:
Computer System Engineering: MIT
Programming Languages:
Principles of Programming Languages: IIT
Security:
Introduction to IT Security: Thammasat University
Security and Cryptography: Thammasat University
Cryptography:
Bilinear Pairings in Cryptography: BIU
App Development:
iPhone Application Development: ITU
Android Application Development: ITU
Artificial Intelligence:
Artificial Intelligence: HRW
Artificial Intelligence: Berkeley
Graphics:
Computer Graphics: Berkeley
Math:
Statistics and Probability: Harvard
Probabilistic Systems Analysis and Applied Probability: MIT
 

Fou-Lu

Member
Looks like it's basically just a list of courses that are freely available from some pretty good institutions. I mean, yeah, of course the content is good. I'm sure the content put out by MIT, Harvard and Stanford is worth your time going through as an educational exercise. But you seem to be doing this for the purposes of getting a job at the end, in which case I'd say that if you're not actually going to get a piece of paper that says BS in CompSci on it, then you're kind of dragging yourself through a lot of mucky trenches when you should probably be focusing on building a portfolio and learning skills that are more directly applicable to an entry level job.

Fair enough. What kind of skills are directly applicable for an entry level development job?
 

ricki42

Member
If I want to career change to a software developer/possible game dev and have only really used code for statistics and physics purposes, which courses would you recommend I go through? I have been considering going to UBC for their BCS program, which lets you get a second bachelor's in CS in two years, but since I already use programming for my Physics research I thought self-teaching might be more viable.

I recently did the same thing. I come from a physics background, had no CS / programming classes in university at all, but had to learn programming for my research. Decided I didn't want to stay in academia and started applying for programming jobs last summer, started my new job as software engineer in January. I still haven't taken any CS courses, just watched some youtube videos and read a bit about algorithms and data structures to prepare for interviews. Also did a bunch of topcoder and codewars exercises and some private projects to practice the stuff I read about.
I tried applying at several game studios, but the furthest I got was a phone interview. The coding was not a problem, but they basically told me that everyone else who applied already had several years of game development experience from internships and such. So I think it may be hard getting into game development from a physics background, and it would probably be more useful to spend your time writing games than taking general CS courses.
 

Fou-Lu

Member
I recently did the same thing. I come from a physics background, had no CS / programming classes in university at all, but had to learn programming for my research. Decided I didn't want to stay in academia and started applying for programming jobs last summer, started my new job as software engineer in January. I still haven't taken any CS courses, just watched some youtube videos and read a bit about algorithms and data structures to prepare for interviews. Also did a bunch of topcoder and codewars exercises and some private projects to practice the stuff I read about.
I tried applying at several game studios, but the furthest I got was a phone interview. The coding was not a problem, but they basically told me that everyone else who applied already had several years of game development experience from internships and such. So I think it may be hard getting into game development from a physics background, and it would probably be more useful to spend your time writing games than taking general CS courses.

This is really encouraging! Thank you for sharing your experience.
 

Moosichu

Member
Yes, the memory is allocated when you first create the array (which is why the memory allocation happens outside, not inside the loop).

At first I thought, "I'm not creating an array at that point though", however, I then realised that I am using a custom "getter" to retrieve the heightmap variable. I had forgotten that, and that is what has been causing the funky issues.

I still don't know if using `get` and `set` is a good idea or not though.

Thank you!
 

Makai

Member
C9f22hJVoAAO6-B.jpg:large
 
Uhh is this reddit?

Looks like Reddit, but I think that is a joke.
Firstly, the password is not displayed when you sign up, and secondly you don't get that message if you use an existing password (just try with your own). It's probably just somebody having fun with the page inspection tools in for example Chrome.
 

Jokab

Member
I'm using FFMPEG to convert a Discord (the desktop app) PCM audio stream to an encoded file in node. Problem is that my audio comes out way lower pitch in the file than if I play it back to Discord again. The same thing happens both with my FFMPEG node lib and with FFMPEG in the terminal. I'm really not very familiar with voice, but why could this be happening? I'm not using any output settings, just telling FFMPEG what format my audio is input in (signed 16-bit little endian, 44.1k Hz with 2 channels) and then outputing to an mp3 file.
 

Koren

Member
I'm using FFMPEG to convert a Discord (the desktop app) PCM audio stream to an encoded file in node. Problem is that my audio comes out way lower pitch in the file than if I play it back to Discord again. The same thing happens both with my FFMPEG node lib and with FFMPEG in the terminal. I'm really not very familiar with voice, but why could this be happening? I'm not using any output settings, just telling FFMPEG what format my audio is input in (signed 16-bit little endian, 44.1k Hz with 2 channels) and then outputing to an mp3 file.
Definitively seems to be a frequency issue...

What do you use to play them? Can you check that both are indeed 16-bit, 44.1kHz, 2 channels, according to the software?
 

PantsuJo

Member
Python with threads, doesn't the GIL prevent most performance gains through threads? (unless you mean using subprocess) Anyways.. I think a neat thing would be a command-line based application to download multiple files in parallel. Think wget, but download multiple files at once and potentially with multiple connections per file.
OK, I'm doing this one, I have decided.

Thanks for the tip, it seems a cool idea!

I already love Python ^^
 

balgajo

Member
Do you guys know some good website for C++ freelancer jobs?

I work fulltime here in Brazil with C++/Qt/Embedded and my salary is about $5,30 per hour. That's low even for Brazilian standards. I'll try something new...
 

Jokab

Member
Definitively seems to be a frequency issue...

What do you use to play them? Can you check that both are indeed 16-bit, 44.1kHz, 2 channels, according to the software?

Had time to check it now. I'm using VLC to play, though it sounds the same when played in browser for example. FFMPEG from the terminal indeed outputs 16-bit, 44.1kHz and 2 channels. The file output from the lib doesn't specify sampling bits, but I assume it's the same since it sounds exactly the same as the terminal version.

Just now I tried changing it to 48kHz and 46kHz, and I'm not sure which sounds more normal... They sound better than 44.1kHz for sure, but yeah. How would I know which one is 'correct'? Again, I'm a novice to dealing with audio so any advice is helpful.

EDIT:
If I don't specify any output frequency for FFMPEG, it gives me this:
Code:
Output #0, wav, to 'file.wav':
  Metadata:
    ISFT            : Lavf57.66.103
    Stream #0:0: Audio: pcm_s16le ([1][0][0][0] / 0x0001), 44100 Hz, stereo, s16, 1411 kb/s
    Metadata:
      encoder         : Lavc57.82.102 pcm_s16le
size=     491kB time=00:00:02.85 bitrate=1411.4kbits/s speed= 947x
video:0kB audio:491kB subtitle:0kB other streams:0kB global headers:0kB muxing overhead: 0.015506%

Seems like the stream it's given is 44.1kHz. Still sounds off.
 

Eridani

Member
Had time to check it now. I'm using VLC to play, though it sounds the same when played in browser for example. FFMPEG from the terminal indeed outputs 16-bit, 44.1kHz and 2 channels. The file output from the lib doesn't specify sampling bits, but I assume it's the same since it sounds exactly the same as the terminal version.

Just now I tried changing it to 48kHz and 46kHz, and I'm not sure which sounds more normal... They sound better than 44.1kHz for sure, but yeah. How would I know which one is 'correct'? Again, I'm a novice to dealing with audio so any advice is helpful.

I found this on github, which says 48kHz is the frequency you want (it's a bit old though). I doubt the correct frequency is anything other than the commonly used ones (which are 44.1kHz, 48kHz - I really doubt discord uses anything higher). So if 48kHz sounds better than 44.1kHz than it's likely the correct one.
 

Jokab

Member
I found this on github, which says 48kHz is the frequency you want (it's a bit old though). I doubt the correct frequency is anything other than the commonly used ones (which are 44.1kHz, 48kHz - I really doubt discord uses anything higher). So if 48kHz sounds better than 44.1kHz than it's likely the correct one.

Oh, that makes a lot of sense. Not sure why I didn't google the exact issue. Thanks :)
 

wwm0nkey

Member
hmmmm I can't seem to find out what is causing this invalid cast error, it happens at

Code:
customerToReturn = GetCustomer((int)objNewCustomerId);
but I don't exactly know what is wrong since it gives me 0 info about the error other than it was an invalid cast....but the code also works, like it adds a customer to my DB but crashes after that.

Here is the full function, if anyone could give me any ideas that would be amazing

Code:
public Customer AddCustomerToDB(Customer newCustomer) {
            Customer customerToReturn;

            SqlCommand cmd = GetDbCommand();

            //Setup our SELECT statement (sql)
            cmd.CommandText = @"
                INSERT INTO [AdventureWorksLT2012].[SalesLT].[Customer]
                (NameStyle, Title, FirstName, MiddleName, LastName, Suffix, CompanyName, SalesPerson,
                EmailAddress, Phone, PasswordHash, PasswordSalt)
                VALUES
                (@NameStyle, @Title, @FirstName, @MiddleName, @LastName, @Suffix, @CompanyName, @SalesPerson,
                @EmailAddress, @Phone, @PasswordHash, @PasswordSalt);
                SELECT @@Identity from [AdventureWorksLT2012].[SalesLT].[Customer]
                ";

            cmd.Parameters.AddWithValue("@NameStyle", newCustomer.NameStyle);
            cmd.Parameters.AddWithValue("@Title", newCustomer.Title);
            cmd.Parameters.AddWithValue("@FirstName", newCustomer.FirstName);
            cmd.Parameters.AddWithValue("@MiddleName", newCustomer.MiddleName);
            cmd.Parameters.AddWithValue("@LastName", newCustomer.LastName);
            cmd.Parameters.AddWithValue("@Suffix", newCustomer.Suffix);
            cmd.Parameters.AddWithValue("@CompanyName", newCustomer.CompanyName);
            cmd.Parameters.AddWithValue("@SalesPerson", newCustomer.SalesPerson);
            cmd.Parameters.AddWithValue("@EmailAddress", newCustomer.EmailAddress);
            cmd.Parameters.AddWithValue("@Phone", newCustomer.Phone);
            cmd.Parameters.AddWithValue("@PasswordHash", newCustomer.PasswordHash);
            cmd.Parameters.AddWithValue("@PasswordSalt", newCustomer.PasswordSalt);
            //cmd.Parameters.AddWithValue("@RowGuid", newCustomer.RowGuid);

            object objNewCustomerId;
            try 
            {
                cmd.Connection.Open();
                objNewCustomerId= cmd.ExecuteScalar();
                cmd.Connection.Close();
            } 
            catch (Exception ex) 
            {
                throw;
            }

            customerToReturn = GetCustomer((int)objNewCustomerId);

            return customerToReturn;
        }
 

Somnid

Member
hmmmm I can't seem to find out what is causing this invalid cast error, it happens at

Code:
customerToReturn = GetCustomer((int)objNewCustomerId);
but I don't exactly know what is wrong since it gives me 0 info about the error other than it was an invalid cast....but the code also works, like it adds a customer to my DB but crashes after that.

Here is the full function, if anyone could give me any ideas that would be amazing

Code:
public Customer AddCustomerToDB(Customer newCustomer) {
            Customer customerToReturn;

            SqlCommand cmd = GetDbCommand();

            //Setup our SELECT statement (sql)
            cmd.CommandText = @"
                INSERT INTO [AdventureWorksLT2012].[SalesLT].[Customer]
                (NameStyle, Title, FirstName, MiddleName, LastName, Suffix, CompanyName, SalesPerson,
                EmailAddress, Phone, PasswordHash, PasswordSalt)
                VALUES
                (@NameStyle, @Title, @FirstName, @MiddleName, @LastName, @Suffix, @CompanyName, @SalesPerson,
                @EmailAddress, @Phone, @PasswordHash, @PasswordSalt);
                SELECT @@Identity from [AdventureWorksLT2012].[SalesLT].[Customer]
                ";

            cmd.Parameters.AddWithValue("@NameStyle", newCustomer.NameStyle);
            cmd.Parameters.AddWithValue("@Title", newCustomer.Title);
            cmd.Parameters.AddWithValue("@FirstName", newCustomer.FirstName);
            cmd.Parameters.AddWithValue("@MiddleName", newCustomer.MiddleName);
            cmd.Parameters.AddWithValue("@LastName", newCustomer.LastName);
            cmd.Parameters.AddWithValue("@Suffix", newCustomer.Suffix);
            cmd.Parameters.AddWithValue("@CompanyName", newCustomer.CompanyName);
            cmd.Parameters.AddWithValue("@SalesPerson", newCustomer.SalesPerson);
            cmd.Parameters.AddWithValue("@EmailAddress", newCustomer.EmailAddress);
            cmd.Parameters.AddWithValue("@Phone", newCustomer.Phone);
            cmd.Parameters.AddWithValue("@PasswordHash", newCustomer.PasswordHash);
            cmd.Parameters.AddWithValue("@PasswordSalt", newCustomer.PasswordSalt);
            //cmd.Parameters.AddWithValue("@RowGuid", newCustomer.RowGuid);

            object objNewCustomerId;
            try 
            {
                cmd.Connection.Open();
                objNewCustomerId= cmd.ExecuteScalar();
                cmd.Connection.Close();
            } 
            catch (Exception ex) 
            {
                throw;
            }

            customerToReturn = GetCustomer((int)objNewCustomerId);

            return customerToReturn;
        }

What is the the value of objNewCustomerId as it comes back (you might want to set a breakpoint and debug)? It should be the last identity column value but is that castable to an int? The other possibilities I can't rule out from just this snippet is that GetCustomer's parameter not actually an int or GetCustomer doesn't return an Customer.
 
I think the problem is that this is a batch statement. i.e. an INSERT followed by a SELECT. I don't think a statement such as this returns anything, so you really should be calling ExecuteNonQuery. If you want to get the result of one of the statements, that has to be the only statement, so you should be running the INSERT first with ExecuteNonQuery(), and then the SELECT second with ExecuteScalar()
 

Zoe

Member
You can get an output from ExecuteNonQuery(). Store the Identity into a parameter and set the ParameterDirection to output.

I would probably wrap another try/catch around the customerToReturn assignment though, or do a check for DBNull first.
 

Somnid

Member
Hello all. Just in here to complain about multithreading. Its dark magic and only wizards understand it.

Let me tell you about my friend Rust.

Note: Concurrency in Rust is still very hard to wrap your head around, but it offers no footguns, if it compiles you have no concurrency issues.
 

ColdPizza

Banned
hmmmm I can't seem to find out what is causing this invalid cast error, it happens at

Code:
customerToReturn = GetCustomer((int)objNewCustomerId);
but I don't exactly know what is wrong since it gives me 0 info about the error other than it was an invalid cast....but the code also works, like it adds a customer to my DB but crashes after that.

Here is the full function, if anyone could give me any ideas that would be amazing

Code:
public Customer AddCustomerToDB(Customer newCustomer) {
            Customer customerToReturn;

            SqlCommand cmd = GetDbCommand();

            //Setup our SELECT statement (sql)
            cmd.CommandText = @"
                INSERT INTO [AdventureWorksLT2012].[SalesLT].[Customer]
                (NameStyle, Title, FirstName, MiddleName, LastName, Suffix, CompanyName, SalesPerson,
                EmailAddress, Phone, PasswordHash, PasswordSalt)
                VALUES
                (@NameStyle, @Title, @FirstName, @MiddleName, @LastName, @Suffix, @CompanyName, @SalesPerson,
                @EmailAddress, @Phone, @PasswordHash, @PasswordSalt);
                SELECT @@Identity from [AdventureWorksLT2012].[SalesLT].[Customer]
                ";

            cmd.Parameters.AddWithValue("@NameStyle", newCustomer.NameStyle);
            cmd.Parameters.AddWithValue("@Title", newCustomer.Title);
            cmd.Parameters.AddWithValue("@FirstName", newCustomer.FirstName);
            cmd.Parameters.AddWithValue("@MiddleName", newCustomer.MiddleName);
            cmd.Parameters.AddWithValue("@LastName", newCustomer.LastName);
            cmd.Parameters.AddWithValue("@Suffix", newCustomer.Suffix);
            cmd.Parameters.AddWithValue("@CompanyName", newCustomer.CompanyName);
            cmd.Parameters.AddWithValue("@SalesPerson", newCustomer.SalesPerson);
            cmd.Parameters.AddWithValue("@EmailAddress", newCustomer.EmailAddress);
            cmd.Parameters.AddWithValue("@Phone", newCustomer.Phone);
            cmd.Parameters.AddWithValue("@PasswordHash", newCustomer.PasswordHash);
            cmd.Parameters.AddWithValue("@PasswordSalt", newCustomer.PasswordSalt);
            //cmd.Parameters.AddWithValue("@RowGuid", newCustomer.RowGuid);

            object objNewCustomerId;
            try 
            {
                cmd.Connection.Open();
                objNewCustomerId= cmd.ExecuteScalar();
                cmd.Connection.Close();
            } 
            catch (Exception ex) 
            {
                throw;
            }

            customerToReturn = GetCustomer((int)objNewCustomerId);

            return customerToReturn;
        }
My nitpick here is that you should you probably put that (int)objNewCustomerId on its own line for better debugability or make objNewCustomerId an int and put the cast on the cmd.ExecuteScalar().
 

wwm0nkey

Member
My nitpick here is that you should you probably put that (int)objNewCustomerId on its own line for better debugability or make objNewCustomerId an int and put the cast on the cmd.ExecuteScalar().

Yeah I know but the teacher wants us to turn it in his way. I fixed it though I just put a
Code:
Convert.ToInt32()
and it worked just fine.
 
Yeah I know but the teacher wants us to turn it in his way. I fixed it though I just put a
Code:
Convert.ToInt32()
and it worked just fine.

Just as an FYI, @@Identity can be cast to decimal, which you can then further cast to int. You can't unbox a decimal from object directly to integer.

Code:
object obj = 10.0M; // boxed decimal (your @@IDENTITY)

//invalid
int x = (int)obj;

// valid
int y = (int)(decimal)obj;
 
Being pedantic, Convert.ToUint32 is probably better than casting to a decimal first, because casting to a decimal first relies on the same underlying assumption that caused this to fail when he tried to cast to an int -- that you know what type it is.

Convert.ToUint32() will just work.
 
Being pedantic, Convert.ToUint32 is probably better than casting to a decimal first, because casting to a decimal first relies on the same underlying assumption that caused this to fail when he tried to cast to an int -- that you know what type it is.

Convert.ToUint32() will just work.

You should know what type it is, though. Use whatever conversion mechanism you want, but knowledge of the type is something you should have. @@Identity is a decimal.

Ultimately, you should know why something works rather than simply being happy that it does. Too many developers fall into the latter category.
 

squidyj

Member
I want to generate a dynamically biased random selection.IE if I randomly select between 1 and 10 i can dynamically assign each value from 1 through 10 with a different probability of being selected.

Let n be the size of the set I am selecting from.
Currently I have a binary tree structure where nodes reference the items to be selected.
I can construct it in O(n), update an element in O(log n) and query it in O(log n). There are also no more than n nodes in the tree (by construction, obviously) and an additional n separate references to the nodes for update.

I'm wondering if there's a more efficient answer. Particularly a solution that is appropriate for large values of n.
 
I want to generate a dynamically biased random selection.IE if I randomly select between 1 and 10 i can dynamically assign each value from 1 through 10 with a different probability of being selected.

Let n be the size of the set I am selecting from.
Currently I have a binary tree structure where nodes reference the items to be selected.
I can construct it in O(n), update an element in O(log n) and query it in O(log n). There are also no more than n nodes in the tree (by construction, obviously) and an additional n separate references to the nodes for update.

I'm wondering if there's a more efficient answer. Particularly a solution that is appropriate for large values of n.

Not sure I understand. What does a random selection have to do with a binary tree? If you have N elements, just put them in an array and generate a random number k from 1 to N and access the k'th element. O(1)
 

squidyj

Member
Not sure I understand. What does a random selection have to do with a binary tree? If you have N elements, just put them in an array and generate a random number k from 1 to N and access the k'th element. O(1)

it's the biasing of the result, some things need to be more likely than others and those probabilities need to be able to change frequently. i can't just roll from 1 to n as that doesn't allow me to bias the result correctly.

example over 5 values (0 1 2 3 4)
for the first few rolls we might have
p(0) = p(1) = p(2) = p(3) = 0.125
p(4) = 0.5

then we might want to change it to
p(0) = 0.1
p(1) = 0.2
p(2) = 0.1
p(3) = 0.35
p(4) = 0.25

In my application the actual probability of selection doesn't need to be exact but it's valuable to be able to efficiently make one or a small subset of results more or less probable efficiently.
The solution I've seen to a biased result is binary searching a cumulative probability table and my tree approach works in a similar manner with the benefit of a more efficient update.
 
it's the biasing of the result, some things need to be more likely than others and those probabilities need to be able to change frequently. i can't just roll from 1 to n as that doesn't allow me to bias the result correctly.

example over 5 values (0 1 2 3 4)
for the first few rolls we might have
p(0) = p(1) = p(2) = p(3) = 0.125
p(4) = 0.5

then we might want to change it to
p(0) = 0.1
p(1) = 0.2
p(2) = 0.1
p(3) = 0.35
p(4) = 0.25

In my application the actual probability of selection doesn't need to be exact but it's valuable to be able to efficiently make one or a small subset of results more or less probable efficiently.
The solution I've seen to a biased result is binary searching a cumulative probability table and my tree approach works in a similar manner with the benefit of a more efficient update.

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
 

Koren

Member
Currently I have a binary tree structure where nodes reference the items to be selected.
I can construct it in O(n), update an element in O(log n) and query it in O(log n). There are also no more than n nodes in the tree (by construction, obviously) and an additional n separate references to the nodes for update.
How are your probabilities updated exactly?

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(n)) update for each single probability update will not be interesting compared to a O(n) reconstruction... and in the case you lose the advantage of a O(log(n)) update, a simple dichotomic research over a cumulative table with also be O(n) construction and O(log(n)) 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)
 
How are your probabilities updated exactly?

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(n)) update for each single probability update will not be interesting compared to a O(n) reconstruction... and in the case you lose the advantage of a O(log(n)) update, a simple dichotomic research over a cumulative table with also be O(n) construction and O(log(n)) 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)

using a big table :). But if you can deal with just 1 decimal of precision on the probabilities, you really only need a table with 1000 items. 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
 
Top Bottom