|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On December 10 2017 21:39 Excludos wrote:Show nested quote +On December 10 2017 20:40 sc-darkness wrote:On December 10 2017 19:53 Hanh wrote:On December 09 2017 22:46 sc-darkness wrote:
Mutability isn't difficult in C++. You just pass objects by const reference. I don't know how C# would do it though.
Practically, const is more trouble than what it is worth especially when working with 3rd party libraries that do not use constness. I think you're a minority here. Most C++ developers appreciate const correctness. Yes, sometimes you can't pass a const reference but there will always be such cases even with your own C++ classes. I mean it's not that difficult to just clone a const variable before passing it if that's needed. That said I rarely use it myself. It's not that difficult to keep track of a variable and just not set it again if you need to. And if it can be defined before compile I just use #define instead (That said I don't really have an opinion on the subject. It's more preference than anything else).
I still like to have function heads declaring references as const whenever possible.
Especially when revisiting old code or other people code, it is useful to know if this is passed as reference only to accelerate the code or if it is passed as reference because the function intends to modify it.
And no "if you want the variable to be kept intact, just clone it" is not a viable solution.
|
On December 10 2017 22:43 mahrgell wrote:Show nested quote +On December 10 2017 21:39 Excludos wrote:On December 10 2017 20:40 sc-darkness wrote:On December 10 2017 19:53 Hanh wrote:On December 09 2017 22:46 sc-darkness wrote:
Mutability isn't difficult in C++. You just pass objects by const reference. I don't know how C# would do it though.
Practically, const is more trouble than what it is worth especially when working with 3rd party libraries that do not use constness. I think you're a minority here. Most C++ developers appreciate const correctness. Yes, sometimes you can't pass a const reference but there will always be such cases even with your own C++ classes. I mean it's not that difficult to just clone a const variable before passing it if that's needed. That said I rarely use it myself. It's not that difficult to keep track of a variable and just not set it again if you need to. And if it can be defined before compile I just use #define instead (That said I don't really have an opinion on the subject. It's more preference than anything else). I still like to have function heads declaring references as const whenever possible. Especially when revisiting old code or other people code, it is useful to know if this is passed as reference only to accelerate the code or if it is passed as reference because the function intends to modify it. And no "if you want the variable to be kept intact, just clone it" is not a viable solution.
Never stated the last thing. I said "if you want to pass (or alter) a const variable, you can clone it". That is a perfectly viable solution. Cloning a variable is not what's going to bog down your program even in the slightest.
|
here is a situation I have (python)
I have a set, with many tuples in it. each tuple is of form (a, b, c).
I want to find all tuples in the set of form (a, _, c).
I am guessing that python isn't going to let me use wildcards. So what is the best way to do this? I don't want to have to iterate the set, that defeats the point.
edit: To pre-empt a possible answer, I will say that I can't use a dictionary to solve this problem, because I already am using a dictionary to store my sets. The key for the dictionary is a, not (a,c), because I need to do lookups by a somewhere else.
|
filter and a lambda function?
|
list/set comprehension?
[x for x in s if condition]
|
On December 11 2017 07:57 travis wrote:
here is a situation I have (python)
I have a set, with many tuples in it. each tuple is of form (a, b, c).
I want to find all tuples in the set of form (a, _, c).
I am guessing that python isn't going to let me use wildcards. So what is the best way to do this? I don't want to have to iterate the set, that defeats the point.
edit: To pre-empt a possible answer, I will say that I can't use a dictionary to solve this problem, because I already am using a dictionary to store my sets. The key for the dictionary is a, not (a,c), because I need to do lookups by a somewhere else.
Assume by and b, you mean pattern matching any values instead of specific instances.
You already have a map with key of "a's"
thinking you dict[a] has data like this:
dict[a] = [
(a,x,b),(a,y,b),
(a,x,c),(a,y,c),
(a,x,d),(a,y,d),
]
thrids = set(map(dict[a], lambda x: x[2])) # [b,c,d]
filtered = filter(dict[a], lambda x: x[2] in thirds)
a_and_b = map(filtered , lambda x : (x[0], x[2])) # [(a,b),(a,b),(a,c),(a,c),(a,d),(a,d)]
or
a_and_b = [(x[0],x[1]) for x in filtered]
If you didn't and want to match a specific instance of b:
filtered = filter(dict[a], lambda x: x[2] == b)
a_and_b = [(x[0],x[1]) for x in filtered]
Why are you limited to only using 1 set?
|
edit: nevermind, figured this problem out
anyways i will read those responses i promise, just super busy coding right this moment!
|
Ok! replying to the answers
On December 11 2017 08:21 Acrofales wrote:
filter and a lambda function?
this is something i need to learn  i've seen people doing it a bit but I didn't really understand what was going on
On December 11 2017 08:29 mahrgell wrote:
list/set comprehension?
[x for x in s if condition]
I think this will make me iterate through the set? I want to avoid having to do that so I can have that sweet O(1) lookup.
On December 11 2017 11:18 Neshapotamus wrote:
Assume by and b, you mean pattern matching any values instead of specific instances.
You already have a map with key of "a's"
thinking you dict[a] has data like this:
dict[a] = [
(a,x,b),(a,y,b),
(a,x,c),(a,y,c),
(a,x,d),(a,y,d),
]
thrids = set(map(dict[a], lambda x: x[2])) # [b,c,d]
filtered = filter(dict[a], lambda x: x[2] in thirds)
a_and_b = map(filtered , lambda x : (x[0], x[2])) # [(a,b),(a,b),(a,c),(a,c),(a,d),(a,d)]
or
a_and_b = [(x[0],x[1]) for x in filtered]
If you didn't and want to match a specific instance of b:
filtered = filter(dict[a], lambda x: x[2] == b)
a_and_b = [(x[0],x[1]) for x in filtered]
Why are you limited to only using 1 set?
more lambda stuff, I will have to read up on it.
I can't answer your actual question about only using 1 set, because my approach changed. But I wasn't only using one set, I was using many sets. I can't remember the details though.
Anyways, something I want to bring up. I've built a TSP algorithm that seems to give the optimal solution (as in, solves the problem). I've been working on methods for a while and all of them were focused on providing the actual answer, not just a best approximation.
Intuitively, it makes sense that it solves it to me. Mathematically, I get flustered when n gets large, I think I would need a math guy to help prove it. And I'd need to see if someone else has taken this approach. I compared it to brute force up to n=11 (any higher and brute force takes forever), about 100 times. It matched brute force every time.
The algorithm is not fast, but it is much much faster than brute force.
Analyzing the complexity would take some time, and I think there is a shitload of optimizing I can do. (hell, there may even be ways to creatively utilize the overall concept to drastically cut runtime down even more).
average runtimes (timing with a clock) looked like this. set up time (populating edges and loading imports) is included in both times.
n = 10
brute force: 12 seconds
mine: 3 seconds
n = 11
brute force: 75 seconds
mine: 12 seconds
n=12
brute force: I don't want to wait this long. I am guessing 25-30 minutes
mine: 1 minute, 5 seconds
Is this at all impressive, assuming the algorithm actually solves every tsp problem assigned?
I'll try a problem set from a repository tonight while I sleep. See if I can solve ~50 or something. I don't exactly have a super computer.
|
Pick one:
[ ] use (hash based) set
[ ] do your search in O(1)
|
On December 12 2017 02:27 travis wrote:
n = 10
brute force: 12 seconds
mine: 3 seconds
n = 11
brute force: 75 seconds
mine: 12 seconds
n=12
brute force: I don't want to wait this long. I am guessing 25-30 minutes
mine: 1 minute, 5 seconds
Is this at all impressive, assuming the algorithm actually solves every tsp problem assigned?
Hard to say with low n. There exist a bunch of exact algorithms and heuristic solutions to tsp. Every exact solution is some variant of worst case 2^n * some additional polynomial. So make n large and it doesn't really matter. Smear some A* on that and call it day.
With your 3 data points (10,3); (11,12); (12,65), it sounds like it's still exponential?
If you managed to find a not-exponential exact solution to tsp, you should probably like, not post on this forum anymore, and go collect your fields medal and/or turing award. Also a million dollars.
|
Why not both? He can collect awards and still post here!
Edit: Not that i am making fun of Travis. I dont know shit about algorithms.
|
On December 12 2017 17:26 Silvanel wrote:
Why not both? He can collect awards and still post here!
Edit: Not that i am making fun of Travis. I dont know shit about algorithms.
Algorithms are for pussies  Real men solve their problems the hard way.
|
On December 13 2017 00:32 Manit0u wrote:Show nested quote +On December 12 2017 17:26 Silvanel wrote:
Why not both? He can collect awards and still post here!
Edit: Not that i am making fun of Travis. I dont know shit about algorithms. Algorithms are for pussies Real men solve their problems the hard way.
Somehow when you say that, I'm picturing my grandpa, who when given 2 dozen German cities and the task to drive the shortest route, would claim to know this perfect route faster than any algorithm could even process the input.
And then he would start driving without ever looking back and having a single doubt.
I guess this could then be described as "the hard way" for any potential co-drivers.
|
On December 12 2017 12:55 phar wrote:Show nested quote +On December 12 2017 02:27 travis wrote:
n = 10
brute force: 12 seconds
mine: 3 seconds
n = 11
brute force: 75 seconds
mine: 12 seconds
n=12
brute force: I don't want to wait this long. I am guessing 25-30 minutes
mine: 1 minute, 5 seconds
Is this at all impressive, assuming the algorithm actually solves every tsp problem assigned?
Hard to say with low n. There exist a bunch of exact algorithms and heuristic solutions to tsp. Every exact solution is some variant of worst case 2^n * some additional polynomial. So make n large and it doesn't really matter. Smear some A* on that and call it day. With your 3 data points (10,3); (11,12); (12,65), it sounds like it's still exponential? If you managed to find a not-exponential exact solution to tsp, you should probably like, not post on this forum anymore, and go collect your fields medal and/or turing award. Also a million dollars.
Essentially this.
As a side note, if you check the Wikipedia page, it mentions that there's an early dynamic programming solution that is O(n^2 * 2^n), while the brute force solution is O(n!). If you look at those two running times while ignoring constants, you get something like this:
n n! n^2*2^n
0 1 0
1 1 2
2 2 16
3 6 72
4 24 256
5 120 800
6 720 2304
7 5040 6272
8 40320 16384
9 362880 41472
10 3628800 102400
11 39916800 247808
in which the dynamic programming solution starts overtaking brute force around n=7, and really beating it as you get up into the 9-11 range. Without a larger sample size from your algorithm vs. brute force or the algorithm itself, we can't say if you've got a qualitatively superior (but still exponential) solution like the DP one, or have just managed to bring down the constant on brute force.
If you want to post the approach, I'd be happy to see if I can find any flaws in the logic and/or prove it =) Algorithms was always my favorite subject.
|
Do you guys think that inventors of algorithms should be able to patent them?
I read lots of arguments that no they shouldn't, but it doesn't seem any different than discoveries in other scientific fields, to me.
Furthermore, it would seem wrong for some scientist to develop an algorithm and then make little or no financial gain from it, while megacorporations with huge amounts of infastructure can immediately utilize it to increase their profits.
|
If you want the actual answer, from a patent law perspective, you want to do the following:
First read the old trilogy (Gottschalk v. Benson, Parker v. Flook, and Diamond v. Diehr).
And then go look up the recent-ish rulings on Mayo v. Prometheus, Alice v. CLS, and potentially Bilski v. Kappos. Long story short, it's not a purely settled matter yet. However:
Abstract ideas cannot be patented, that's a sure thing. Math, laws of nature, etc cannot be patented, that's a sure thing. As in Gottshalk v. Benson, pure algorithms tend to fall into those categories - not patentable. Meaning if you came up with an exponential solution to TSP, it probably would not be patentable.
That said, if you came up with a way of combining more complex software systems to do some novel thing, you can probably get a patent on it. Whether or not it would hold light in court with sufficient money thrown against you from the other side, is up to how novel your new system is, and maybe whether or not you draw Judge Aslup on the district court level 
^ The above is not really my opinion on the way things should be, but rather the way things actually are for US patent law today. So I say this not as a computer person, but as second hand knowledge from someone else who knows a damn shit ton about patent law. So also I could be misremembering / misconstruing some things...
From a practical perspective, there is a reason why a lot of companies don't open source their core algorithms. Trade secrets yo. If a scientist comes up with a sufficiently brilliant algo, they can monetize. See e.g. Larry Page & Sergey Brin, who came up with PageRank, and now are the 12th & 13th richest people in the world.
|
That's also why you can't really patent/copyright game mechanics since they're usually just math algorithms.
|
But how is that different than divising a formula or recipe for a chemical, medicine, material, etc? That's also just math. It's literally a an algorithm. So why is it commonly accepted that patents for this makes sense, but patents for digital recipes do not?
I think the distinction is arbitrary and unfair.
(that said, you actually can patent algorithms and ideas, if properly presented to the patent office. but you aren't supposed to be able to)
|
On December 13 2017 19:56 travis wrote:
But how is that different than divising a formula or recipe for a chemical, medicine, material, etc? That's also just math. It's literally a an algorithm. So why is it commonly accepted that patents for this makes sense, but patents for digital recipes do not?
I think the distinction is arbitrary and unfair.
(that said, you actually can patent algorithms and ideas, if properly presented to the patent office. but you aren't supposed to be able to)
Let's just be thankful that we can't. If people had the option of patenting algorithms we'd be set back years.
|
On December 13 2017 11:25 travis wrote:
Do you guys think that inventors of algorithms should be able to patent them?
I read lots of arguments that no they shouldn't, but it doesn't seem any different than discoveries in other scientific fields, to me.
Furthermore, it would seem wrong for some scientist to develop an algorithm and then make little or no financial gain from it, while megacorporations with huge amounts of infastructure can immediately utilize it to increase their profits.
If you come up with a genius algorithm, don't patent it, because it's probably an abstract idea and thus unpatentable.
Software patents are stupid, but the good ones cover novel systems and methods for solving real life problems. Now if your algorithm can do a million different things (as any truly good solution to the TSP can), then there is not much point in patenting it, because to patent it you also have to divulge it... and you don't want to do that, because that's giving away your unpatentable core technology that can be used for a million different things.
Instead, a brilliant new algorithm is kept as a trade secret and monetized. Either by turning it into a service (e.g. Watson) or by selling services based on it. You could try selling it as a product, but reverse engineering will probably figure out your magic, which is why web-based services is probably the way to go.
Either that, or accept that other people can implement your brilliant algorithm, and just become famous, but not rich off it.
|
|
|
|
|
|
EPT
